import java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-12-23
 * Time: 20:29
 */
public class TestBinarySearch {
    /**
     * 二维数组中的查找(利用有序特征，重二维数组左下开始)
     * @param target
     * @param array
     * @return
     */
    public boolean Find (int target, int[][] array) {
        HashMap<Integer,Integer> map = new HashMap<>();
        Hashtable<Integer,Integer> table = new Hashtable<>();
        ConcurrentHashMap<Integer,Integer> concurrentHashMap = new ConcurrentHashMap<>();

        if (array.length == 0) {
            return false;
        }
        if (array[0].length == 0) {
            return false;
        }
        // 思路：利用有序特征，重二维数组左下开始
        // 先找到二维数组坐下坐标
        int x = 0;
        int y = array.length - 1;
        while (x < array[0].length && y >= 0) {
            if (array[y][x] == target) {
                return true;
            } else if (array[y][x] > target) {
                y--;
            } else {
                x++;
            }
        }
        return false;
    }

    /**
     * 寻找峰值（二分方式）
     * @param nums
     * @return
     */
    public int findPeakElement (int[] nums) {
        // write code here
        // 思路：使用二分方式收缩区间
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[mid + 1]) {
                // 说明此时向左是递增，向左左收缩区间
                right = mid;
            } else {
                // 此时说明是向右递增，向右收缩区间
                left = mid + 1;
            }
        }
        return left;
    }

    /**
     * 找旋转数组中最小的元素
     * 思路：
     *  旋转数组中间元素 > 右边界（最小在右边）
     *  旋转数组中间元素 < 右边界（最小在左边）
     *  旋转数组中间元素 = 右边界（不确定，缩减范围）
     * @param nums
     * @return
     */
    public int minNumberInRotateArray (int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) {
                // 中点值大于右界，在右边
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                // 中点值小于右界，在左边
                right = mid;
            } else {
                // 中点值等于右界，从右缩减区间（因为无法判断在哪）
                right--;
            }
        }
        return nums[left];
    }

    /**
     * 比较版本号（关键在于循环条件是 ||;以及数值计算）
     * @param version1
     * @param version2
     * @return
     */
    public int compare (String version1, String version2) {
        // 分别计算两个版本号的长度
        int v1Len = version1.length();
        int v2Len = version2.length();
        // 定义两个头指针，分别指向v1、v2
        int v1 = 0;
        int v2 = 0;
        // 进行比较
        while (v1 < v1Len || v2 < v2Len) {
            // 计算每个模块version1的值
            int vNum1 = 0;
            while (v1 < v1Len && version1.charAt(v1) != '.') {
                vNum1 = vNum1 * 10 + (version1.charAt(v1) - '0');
                v1 ++;
            }
            // 跳过version1的点
            v1 ++;
            // 计算每个模块version2的值
            int vNum2 = 0;
            while (v2 < v2Len && version2.charAt(v2) != '.') {
                vNum2 = vNum2 * 10 + (version2.charAt(v2) - '0');
                v2 ++;
            }
            // 跳过version2的点
            v2 ++;

            if (vNum1 < vNum2) {
                return -1;
            }
            if (vNum1 > vNum2) {
                return 1;
            }
        }
        return 0;
    }
}
